﻿//#define TRACE_ON
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEulerSolutions.Problems
{
    /*
     * Considering 4-digit primes containing repeated digits it is clear that they cannot all be the same: 1111 is divisible by 11, 2222 is divisible by 22, and so on. But there are nine 4-digit primes containing three ones:

1117, 1151, 1171, 1181, 1511, 1811, 2111, 4111, 8111

We shall say that M(n, d) represents the maximum number of repeated digits for an n-digit prime where d is the repeated digit, N(n, d) represents the number of such primes, and S(n, d) represents the sum of these primes.

So M(4, 1) = 3 is the maximum number of repeated digits for a 4-digit prime where one is the repeated digit, there are N(4, 1) = 9 such primes, and the sum of these primes is S(4, 1) = 22275. It turns out that for d = 0, it is only possible to have M(4, 0) = 2 repeated digits, but there are N(4, 0) = 13 such cases.

In the same way we obtain the following results for 4-digit primes.
Digit, d 	M(4, d) 	N(4, d) 	S(4, d)
0 	2 	13 	67061
1 	3 	9 	22275
2 	3 	1 	2221
3 	3 	12 	46214
4 	3 	2 	8888
5 	3 	1 	5557
6 	3 	1 	6661
7 	3 	9 	57863
8 	3 	1 	8887
9 	3 	7 	48073

For d = 0 to 9, the sum of all S(4, d) is 273700.

Find the sum of all S(10, d).

     * */
    class Problem111 : IProblem
    {
        public string Calculate()
        {
            //M(10,0) = 8;
            //N(10,0) = 2;
            //1000000007;
            //1000000009;
            //S(10,0) = 2000000016;

            //M(10,1) = 9;
            //1111111121;
            //1111111181;
            //1111111411;
            //1111115111;
            //1111211111;
            //1111411111;
            //1115111111;
            //1117111111;
            //1121111111;
            //1151111111;
            //1711111111;
            //N(10,1) = 11;

            long initial = 1111111111;

            SieveOfAtkin sieve = new SieveOfAtkin((int)Math.Sqrt(initial) + 1);


            

            int numDigits = CommonFunctions.NumberOfDigits(initial);
            long maxPower = (long)Math.Pow(10, numDigits - 1);

            long start = 1000000001;
            int count = 0;
            long sum = 0;

            for (long outer = 0; outer <= 9000000000; outer += 1000000000)
            {
                for (long power = 1; power <= 1; power *= 10)
                {
                    for (int digit = 0; digit <= 8; digit += 2)
                    {
                        long n = start + digit * power + outer;
                        bool isPrime = sieve.IsPrime(n);
                        if (isPrime)
                        {
                            count++;
#if TRACE_ON
                            Console.WriteLine(n);
#endif
                            sum += n;
                        }
                    }
                }
            }
#if TRACE_ON
            Console.WriteLine("N(10,0) = {0}", count);
#endif


            int d = 1;
            start = initial * d;
            count = 0;

            for (long power = 1; power <= maxPower; power *= 10)
            {
                for (int digit = -1; digit <= 8; digit += 1)
                {
                    long n = start + digit * power;
                    bool isPrime = sieve.IsPrime(n);
                    if (isPrime)
                    {
                        count++;
#if TRACE_ON
                            Console.WriteLine(n);
#endif
                        sum += n;
                    }
                }
            }
#if TRACE_ON
            Console.WriteLine("N(10,0) = {0}", count);
#endif
            start = initial * (long)2;
            count = 0;

            for (long power2 = 1; power2 <= maxPower; power2 *= 10)
            {
                for (int digit2 = -2; digit2 <= 7; digit2++)
                {
                    if (digit2 == -2 && power2 == maxPower)
                        continue;

                    for (long power = power2 * 10; power <= maxPower; power *= 10)
                    {
                        if (power == power2)
                            continue;

                        for (int digit = -2; digit <= 7; digit += 1)
                        {
                            if (digit == -2 && power == maxPower)
                                continue;
                            long n = start + digit * power + digit2 * power2;
                            if (n < maxPower || n >= maxPower * 10)
                                continue;
                            bool isPrime = sieve.IsPrime(n);
                            if (isPrime)
                            {
                                count++;
#if TRACE_ON
                            Console.WriteLine(n);
#endif
                                sum += n;
                            }
                        }
                    }
                }
            }
#if TRACE_ON
            Console.WriteLine("N(10,0) = {0}", count);
#endif

            d = 3;
            start = initial * (long)d;
            count = 0;

            for (long power = 1; power <= maxPower; power *= 10)
            {
                for (int digit = 0 - d; digit <= 9 - d; digit += 1)
                {
                    long n = start + digit * power;
                    bool isPrime = sieve.IsPrime(n);
                    if (isPrime)
                    {
                        count++;
#if TRACE_ON
                            Console.WriteLine(n);
#endif
                        sum += n;
                    }
                }
            }
#if TRACE_ON
            Console.WriteLine("N(10,0) = {0}", count);
#endif
            d = 4;
            start = initial * (long)d;
            count = 0;

            for (long power = 1; power <= maxPower; power *= 10)
            {
                for (int digit = 0 - d; digit <= 9 - d; digit += 1)
                {
                    long n = start + digit * power;
                    bool isPrime = sieve.IsPrime(n);
                    if (isPrime)
                    {
                        count++;
#if TRACE_ON
                            Console.WriteLine(n);
#endif
                        sum += n;
                    }
                }
            }
#if TRACE_ON
            Console.WriteLine("N(10,0) = {0}", count);
#endif

            d = 5;
            start = initial * (long)d;
            count = 0;

            for (long power = 1; power <= maxPower; power *= 10)
            {
                for (int digit = 0 - d; digit <= 9 - d; digit += 1)
                {
                    long n = start + digit * power;
                    bool isPrime = sieve.IsPrime(n);
                    if (isPrime)
                    {
                        count++;
#if TRACE_ON
                            Console.WriteLine(n);
#endif
                        sum += n;
                    }
                }
            }
#if TRACE_ON
            Console.WriteLine("N(10,0) = {0}", count);
#endif
            d = 6;
            start = initial * (long)d;
            count = 0;

            for (long power = 1; power <= maxPower; power *= 10)
            {
                for (int digit = 0 - d; digit <= 9 - d; digit += 1)
                {
                    long n = start + digit * power;
                    bool isPrime = sieve.IsPrime(n);
                    if (isPrime)
                    {
                        count++;
#if TRACE_ON
                            Console.WriteLine(n);
#endif
                        sum += n;
                    }
                }
            }
#if TRACE_ON
            Console.WriteLine("N(10,0) = {0}", count);
#endif

            d = 7;
            start = initial * (long)d;
            count = 0;

            for (long power = 1; power <= maxPower; power *= 10)
            {
                for (int digit = 0 - d; digit <= 9 - d; digit += 1)
                {
                    long n = start + digit * power;
                    bool isPrime = sieve.IsPrime(n);
                    if (isPrime)
                    {
                        count++;
#if TRACE_ON
                            Console.WriteLine(n);
#endif
                        sum += n;
                    }
                }
            }
#if TRACE_ON
            Console.WriteLine("N(10,0) = {0}", count);
#endif
            start = initial * (long)8;
            count = 0;

            for (long power2 = 1; power2 <= maxPower; power2 *= 10)
            {
                for (int digit2 = -8; digit2 <= 1; digit2++)
                {
                    if (digit2 == -8 && power2 == maxPower)
                        continue;

                    for (long power = power2 * 10; power <= maxPower; power *= 10)
                    {
                        if (power == power2)
                            continue;

                        for (int digit = -8; digit <= 1; digit += 1)
                        {
                            if (digit == -8 && power == maxPower)
                                continue;
                            long n = start + digit * power + digit2 * power2;
                            if (n < maxPower || n >= maxPower * 10)
                                continue;
                            bool isPrime = sieve.IsPrime(n);
                            if (isPrime)
                            {
                                count++;
#if TRACE_ON
                            Console.WriteLine(n);
#endif
                                sum += n;
                            }
                        }
                    }
                }
            }
#if TRACE_ON
            Console.WriteLine("N(10,0) = {0}", count);
#endif
            d = 9;
            start = initial * (long)d;
            count = 0;

            for (long power = 1; power <= maxPower; power *= 10)
            {
                for (int digit = 0 - d; digit <= 9 - d; digit += 1)
                {
                    long n = start + digit * power;
                    bool isPrime = sieve.IsPrime(n);
                    if (isPrime)
                    {
                        count++;
#if TRACE_ON
                            Console.WriteLine(n);
#endif
                        sum += n;
                    }
                }
            }
#if TRACE_ON
            Console.WriteLine("N(10,0) = {0}", count);
#endif
            return sum.ToString();
        }
    }
}
